package leetcode_day._2021._202112._1120;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/12/14 9:15
 * 课程表III
 * 这里有 n 门不同的在线课程，按从 1 到 n 编号。给你一个数组 courses ，其中 courses[i] = [durationi, lastDayi]
 * 表示第 i 门课将会持续上 durationi 天课，并且必须在不晚于 lastDayi 的时候完成。
 * 你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。
 * 返回你最多可以修读的课程数目。
 * 算法：贪心 + 优先队列
 */
public class _14_630 {

    public int scheduleCourse(int[][] courses) {
        // 先将课程按照结束时间从小到大排序, 越早结束，可以选越多的课
        Arrays.sort(courses, Comparator.comparingInt(a -> a[1]));
        // 存储已经选择的课程, 按照持续时间从大到小排序
        PriorityQueue<Integer> ans = new PriorityQueue<>((a, b) -> b - a);
        // 选择课程所花的时间
        int day = 0;
        for (int[] course : courses) {
            if (day + course[0] <= course[1]) {
                day += course[0];
                ans.offer(course[0]);
            } else if (!ans.isEmpty() && ans.peek() > course[0]) {
                // 由于 courses 数组已经排序过了，所以队列中所有课程的结束时间小于当前课程的结束时间
                day -= ans.poll();
                day += course[1];
                ans.offer(course[0]);
            }
        }
        return ans.size();
    }

    public int scheduleCourse2(int[][] courses) {
        Arrays.sort(courses, Comparator.comparingInt(a -> a[1]));
        PriorityQueue<Integer> ans = new PriorityQueue<>((a, b) -> b - a);
        int day = 0;
        for (int[] course : courses) {
            day += course[0];
            ans.offer(course[0]);
            // 如果超出了当前课程的最后结束时间，就要在队列中去掉持续时间最长的课程
            if (day > course[1]) ans.poll();
        }
        return ans.size();
    }

}
